With development of wireless digital communication and emergence of various services with high speed and strong burst, there are increasingly higher demands for the error-correcting coding technology proposed by people. FIG. 1 shows a typical digital communication system. Low density parity check codes (LDPC) is a type of liner block code that can be defined by a very sparse parity check matrix or a bi-partite graph. The LDPC was initially discovered by Gallager, and that's why it is called Gallager codes. After decades of silence, with the development of computer hardware and the relative theories, MacKay and Neal rediscovered the LDPC and demonstrated that the LDPC has performance approaching the Shannon limit. The latest research shows that LDPC has the following advantages: low decoding complexity, being capable of linear-time coding, having performance approaching Shannon limit, being capable of parallel decoding, and superior to Turbo codes in the scenario of large-size codes.
LDPC codes are a type of linear block codes based on a sparse parity check matrix, and the encoding and decoding of low complexity are realized just by utilizing the sparsity of the check matrix of the LDPC codes, thereby making the LDPC codes practicable. Irregular codes refer to low density parity check codes where a row weight and a column weight of a parity check matrix are totally different, and column weights of an information bit portion of the parity check matrix are also different. Irregular codes refer to low density parity check codes where a row weight and a column weight of a parity check matrix are totally same, or low density parity check codes where a row weight and a column weight of an information-bit portion are totally same in a parity check matrix when a check-bit portion correspondingly maintains a constant structure. In the relevant literature, the low density parity codes of the second case of regular codes are named as semi-regular codes. Power number distribution of the basic matrix and power number distribution of the parity check matrix are consistent.
LDPC is a special type of linear block code. In communication, M check bits are needed to guarantee certain correction capability when a codeword with block length of N bits is sent, each codeword needs to meet HxT=0T, herein H is an M×N dimensional parity check matrix in a binary field. All operations are performed in a binary field GF(2), and addition and subtraction herein are “XOR” operation, and multiplication is “AND” operation.
Structured LDPC
Structured LDPC codes, also named as (Quasi-Cyclic)QC-LDPC code, are a special kind of LDPC codes. Structured LDPC codes are very famous and have been adopted and widely used by many communication systems such as WiMAX, 11n, 11ad, 11ac etc. Meanwhile, it is very likely that Structured LDPC codes will be selected as main channel coding scheme for 5G (the 5-th mobile communication system)
A parity check matrix H of the structured LDPC codes is assumed to be an (Mb×z)×(Nb×z) matrix composed of Mb×Nb block matrices, each block matrix is a z×z basic permutation matrix with a different power number or a z×z zero matrix. When the basic permutation matrix is a unit matrix, block matrices are cyclic shift matrices of the unit matrix (the default is right shift in this document). Each block matrix can be uniquely identified via the power number j, the power number of the unit matrix can be represented as 0, and the power number of a matrix is generally represented as −1. Therefore, if each block matrix of H is replaced by its power number, an Mb×Nb power matrix Hb can be obtained. Here, Hb is defined as the basic matrix of H, and H is called the expand matrix of Hb. In practical encoding,
      z    =                  length        ⁢                                  ⁢        of        ⁢                                  ⁢        codeword                    column        ⁢                                  ⁢        number        ⁢                                  ⁢        Nb        ⁢                                  ⁢        of        ⁢                                  ⁢        the        ⁢                                  ⁢        basic        ⁢                                  ⁢        matrix              ,and z is called the expand factor.
Structured LDPC codes, namely (Quasi-Cyclic)QC-LDPC codes, are defined by a base matrix Hb of size Mb×nb, an expanding factor (also named as a lift size) Z and a permutation matrix P of size Z×Z The size of information bits is K=kb×Z, kb=nb−Mb, the size of codeword is N=nb×Z, and the code rate is R=K/N. If each element hbij in the base matrix Hb is replaced by zero sub-block matrix of size Z×Z or the sub-block matrix Phbij, the parity check matrix H of QC-LDPC can be obtained. The base matrix Hb, parity check matrix H and the permutation matrix P are shown as follows:
      Hb    =          [                                                  hb              00                                                          hb              01                                            …                                              hb                              0                ⁢                                  (                                      nb                    -                    1                                    )                                                                                                        hb              10                                                          hb              11                                            …                                              hb                              1                ⁢                                  (                                      nb                    -                    1                                    )                                                                                          …                                …                                …                                …                                                              hb                                                (                                      mb                    -                    1                                    )                                ⁢                0                                                                        hb                                                (                                      mb                    -                    1                                    )                                ⁢                1                                                          …                                              hb                                                (                                      mb                    -                    1                                    )                                ⁢                                  (                                      nb                    -                    1                                    )                                                                        ]            H    =          [                                                  P                              hb                00                                                                        P                              hb                01                                                          …                                              P                              hb                                  0                  ⁢                                      (                                          nb                      -                      1                                        )                                                                                                                          P                              hb                10                                                                        P                              hb                11                                                          …                                              P                              hb                                  1                  ⁢                                      (                                          nb                      -                      1                                        )                                                                                                            …                                …                                …                                …                                                              P                              hb                                                      (                                          mb                      -                      1                                        )                                    ⁢                  0                                                                                        P                              hb                                                      (                                          mb                      -                      1                                        )                                    ⁢                  1                                                                          …                                              P                              hb                                                      (                                          mb                      -                      1                                        )                                    ⁢                                      (                                          nb                      -                      1                                        )                                                                                          ]            P    =          [                                    0                                1                                0                                …                                0                                                0                                0                                1                                …                                0                                                …                                …                                …                                …                                …                                                0                                0                                0                                …                                1                                                1                                0                                0                                …                                0                              ]      Wherein, if hbij==−1 in base matrix, Phbij in H equals a zero matrix of size Z×Z; otherwise, Phbij equals a permutation matrix P to hbij power. The base matrix (Hb) can be divided into 2 parts: systematic part and parity part which are illustrated in FIG. 3. The systematic part includes kb columns (also known as systematic columns) and parity part includes Mb columns (also known as parity columns).
As a extended form, Structured LDPC codes also include multi-edge (ME) LDPC codes, which means that one entry of row i-th and column j-th in the base matrix may include one or two element instead of only one element. Herein, one element of row i-th and column j-th of base matrix means each element of the entry of row i-th and column j-th. By the way, two elements for row i-th and column j-th in the base matrix means that each sub-block matrix is composed by two overlapped circularly shifted matrices.
For example, matrix
  H  =      [                            1                          0                          0                          0                          1                          0                          1                          0                          0                          0                          0                          0                                      0                          1                          0                          0                          0                          1                          0                          1                          0                          0                          0                          0                                      0                          0                          1                          1                          0                          0                          0                          0                          1                          0                          0                          0                                      0                          0                          1                          0                          1                          0                          0                          0                          1                          0                          1                          0                                      1                          0                          0                          0                          0                          1                          1                          0                          0                          0                          0                          1                                      0                          1                          0                          1                          0                          0                          0                          1                          0                          1                          0                          0                      ]                  can be obtained by extending a 2×4 basic matrix Hb and the following parameter z:        
      Z    =    3    ,            and      ⁢                          ⁢              H        b              =          [                                    0                                1                                0                                              -              1                                                            2                                1                                2                                1                              ]      
Therefore, an LDPC encoder of the present document can be uniquely generated by the basic matrix Hb, the expand factor z and the selected basic permutation matrix. In summary, each element in the basic matrix Hb corresponds to a z*z square matrix of the parity check matrix. In particular, in the basic matrix, each element taking the value of −1 corresponds to a z*z zero square matrix, and each element taking the value of non −1 corresponds to a z*z non-zero square matrix (i.e. the unit matrix or the cyclic shift matrices of the unit matrix). According to the above definition of the unit matrix, we can see that under the condition that an expand factor (an integer z greater than 1) is determined, and the base matrix and the parity check matrix are the same in nature.
Encoding of LDPC
A direct encoding method of system block codes is: a codeword x is divided into N−M information bits s and M check bits c, correspondingly, an M×N parity check matrix H is divided into two blocks with sizes of M×(N−M) and M×M corresponding to the information bits and the check bits respectively, namely H[A|B]. According to H×x=0, we can have:
            [              A        |        B            ]        ×          [              s        c            ]        =  0
Then we can have A×s+B×c=0, and further derive c=B−1As. When block B uses a special matrix structure, such as strictly lower triangular structure (half random matrix), double lower triangular structure, etc., B−1 has a very simple form, the check bit part c in the codewords may be directly calculated according to the above formula, and the encoder can be guaranteed to have linear complexity.
Richarson linear-time encoding algorithm may also be applied, the parity check matrix H has quasi lower triangular structure, supposed that H has the following form:
  H  =      (                            A                          B                          T                                      C                          D                          E                      )  
The encoded codewords are supposed to be x=(s, p1, p2), herein s is the system bit part of the encoded codewords, p1 and p2 are the check bit part of the codewords, the length of p1 is g and the length of p2 is (m−g). In the above formula, the dimensions of A are (m−g)×(n−m), the dimensions of B are (m−g)×g, the dimensions of T are (m−g)×(m−g), the dimensions of C are g×(n−m), the dimensions of D are g×g, and the dimensions of E are g×(m−g). All these matrices are sparse matrices, and T is a lower triangular matrix of which all the diagonal elements are 1. The check bit part may be obtained from the following formula:p1T=−φ−1=(−ET−1A+C)sT p2T=−T−1(AsT+Bp1T) herein, φ=−ET−1B+D 
Therefore, the encoder of LDPC codes designed by the present document can be uniquely generated by the LDPC parity check matrix H, which actually determines not only the performance of the LDPC code decoder but also the complexity, storage space and processing delay of the encoder and decoder of LDPC codes. So it is the most important to search for an appropriate parity check matrix structure of LDPC codes.
In a specific implementation, an encoding function for obtaining a codeword of N bits according to source data of N-M bits may be performed by calculating with the foregoing direct method, Richarson method or other methods. In fact, the encoder uses software or hardware to implement the multiplication and addition operations of the sparse matrix in the formula. For LDPC based on the unit matrix and cyclic shift matrix of the unit matrix, the multiplication operation of the sparse matrix may be constituted by several cyclic shift registers with z bits (z is the expand factor) and several adders with z bits, and the addition operation of the sparse matrix may be performed by the foregoing several adders with z bits, and the several cyclic shift registers with z bits and several adders with z bits constitute a LDPC encoder implemented by a hardware circuit.
Decoding of LDPC
A graph presentation of an LDPC parity check matrix is a bipartite graph. The bipartite graph is one-to-one correspondence with the check matrix, an M×N parity check matrix H defines the restriction for each codeword of N bits meeting M parity check sets. One bipartite graph includes N variable nodes and M parity check nodes. When the mth check relates to the nth bit, that is, an element Hm in the mth row and the nth column of the H, when n equals to 1, there will be a connecting line to connect the check node m and the variable node n. There is no connection between nodes of any same kind in the bipartite graph, and the number of edges in the bipartite graph equals to the number of non-zero elements in the check matrix.
The message passing decoding algorithm of LDPC, also called as belief-propagation (BP) algorithm, assumes that the variable nodes are independent with each other, yet the existence of the short circle inevitably breaks the assumption of the independence, which will obviously decrease the decoding performance. In fact, the longer the shortest circle of the bipartite graph corresponding to the LDPC parity check matrix is, that is, the larger the girth value is, the less the positive feedback information transmitted from the variable node to itself is, and the better the decoding performance is. There is a relationship between the girth of the check matrix H and the basic matrix Hb, and the related conclusions can be obtained by validation of mathematical reasoning and computer simulation.
Basic Matrix Correction
If a same basic matrix can not be used for each different expand factor, an LDPC decoder/encoder needs to store one basic matrix for every different code length, then a large number of basic matrices need to be stored when there are a plurality of code lengths, thus a huge storage space will be occupied or the hardware circuit will be complicate.
The correction uses the expand factor of other code length to correct the non-negative elements in the basic matrix Hb, and the corrected element value should be less than the value of the expand factor under the code length. The correction algorithm may be mod, scale+floor or scale+round, etc. Supposed that Pi, j is the non-negative element in the ith row and the jth column of the basic matrix, and P′i, j is the corrected elements, there is:
For a Mod Algorithm:
      P    ij    ′    ≡            P      ij        ⁢                  ⁢    mod    ⁢          n      N      
For a Scale+Floor Algorithm:
      P    ij    ′    =      [                  P        ij            ×              n        2304              ]  
For a Scale+Round Algorithm:
      P    ij    ′    =      Round    ⁡          (                        P          ij                ×                  n          2304                    )                      herein N is the number of columns of the basic matrix, and n is the code length of the low density parity check codes which will generate the parity check matrix. Mod is a mod operation, [ ] is a floor operation, and Round is a rounding operation. Here, the biggest length of codes is supposed to be 2304.        
For example, for low density parity check codes with a code length of 1152 bits, supposed that some non-negative element of the basic matrix is 93, then the corrected result is:
For a Mod Algorithm:
      93    ⁢                  ⁢    mod    ⁢          1152      24        =            93      ⁢                          ⁢      mod      ⁢                          ⁢      48        =    45  
For a Scale+Floor Algorithm:
      [          93      ×              1152        2304              ]    =            [      46.5      ]        =    46  
For a Scale+Round Algorithm:
      Round    ⁢                  ⁢          (              93        ×                  1152          2304                    )        =            Round      ⁡              (        46.5        )              =    47  
If the most recently popular layered decoding is used for LDPC, Read-write of log likelihood ratio information seriously affects the pipelined arrangement of LDPC. In particular, in the high bit rate, for an ordinary LDPC structure, the decoder needs to process one row of the base matrix before beginning the next stage of a pipeline, which needs a long waiting time, and if one stage of a pipeline is particularly long, the efficiency of the decoder will be seriously reduced.